% IEEE Paper Template for US-LETTER Page Size (V1)
% Sample Conference Paper using IEEE LaTeX style file for US-LETTER pagesize.
% Copyright (C) 2006-2008 Causal Productions Pty Ltd.
% Permission is granted to distribute and revise this file provided that
% this header remains intact.
%
% REVISION HISTORY
% 20080211 changed some space characters in the title-author block
%

\documentclass[10pt,conference,letterpaper]{IEEEtran}
\usepackage{times,amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{color}
\usepackage{indentfirst}
\usepackage{url}
\usepackage{graphicx}
\usepackage[font=small,skip=0pt]{caption}
\usepackage[font=small,skip=0pt]{subcaption}
\usepackage[linesnumbered,ruled,lined,boxed,noend]{algorithm2e}
\usepackage{epstopdf}
\usepackage{multirow}
\usepackage{array}
\input{NewCommands}

\newcommand{\Comment}[1]{}  % used for adding my detailed thinking on some questions.
\definecolor{red}{rgb}{1,0,0}

\setlength{\textfloatsep}{5pt}
\setlength{\floatsep}{5pt}
\setlength{\intextsep}{5pt}

\newtheorem{theorem}{Theorem}%[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}{Example}%[section]
\newtheorem{defn}{Definition}%[section]

\newcommand{\reminder}[1]{ {\mbox{$<==$}} [[[ { \bf #1 } ]]] {\mbox{$==>$}}}
\newcommand{\update}[1]{*[{\bf #1 }]*}
\newcolumntype{L}{>{\centering\arraybackslash}m{1.3cm}}
\newcolumntype{S}{>{\centering\arraybackslash}m{1.0cm}}
%
\title{Real Time Personalized Search on Social Networks}
%
%\author{%
%% author names are typeset in 11pt, which is the default size in the author block
%{First Author{\small $~^{\#1}$}, Second Author{\small $~^{*2}$}, Third Author{\small $~^{\#3}$} }%
%% add some space between author names and affils
%\vspace{1.6mm}\\
%\fontsize{10}{10}\selectfont\itshape
%% 20080211 CAUSAL PRODUCTIONS
%% separate superscript on following line from affiliation using narrow space
%$^{\#}$\,First-Third Department, First-Third University\\
%Address Including Country Name\\
%\fontsize{9}{9}\selectfont\ttfamily\upshape
%%
%% 20080211 CAUSAL PRODUCTIONS
%% in the following email addresses, separate the superscript from the email address
%% using a narrow space \,
%% the reason is that Acrobat Reader has an option to auto-detect urls and email
%% addresses, and make them 'hot'.  Without a narrow space, the superscript is included
%% in the email address and corrupts it.
%% Also, removed ~ from pre-superscript since it does not seem to serve any purpose
%$^{1}$\,first.author@first-third.edu\\
%$^{3}$\,third.author@first-third.edu%
%% add some space between email and affil
%\vspace{1.2mm}\\
%\fontsize{10}{10}\selectfont\rmfamily\itshape
%% 20080211 CAUSAL PRODUCTIONS
%% separated superscript on following line from affiliation using narrow space \,
%$^{*}$\,Second Company\\
%Address Including Country Name\\
%\fontsize{9}{9}\selectfont\ttfamily\upshape
%% 20080211 CAUSAL PRODUCTIONS
%% removed ~ from pre-superscript since it does not seem to serve any purpose
%$^{2}$\,second.author@second.com
%}


\author{%
% author names are typeset in 11pt, which is the default size in the author block
{Yuchen Li{\small $~^{\#}$}, Zhifeng Bao{\small $~^{*}$}, Guoliang Li{\small $~^{+}$}, Kian-Lee Tan{\small$~^{\#}$}}\\
% add some space between author names and affils
%\vspace{1.6mm}
\fontsize{10}{10}\selectfont\itshape \hspace{3mm} $~^{\#}$National University of Singapore~~~~~~ $~^{*}$University of Tasmania~~~~~~$~^{+}$Tsinghua University\\
\fontsize{9}{9}\selectfont\ttfamily\upshape
\{liyuchen, tankl\}@comp.nus.edu.sg~~~~~~baoz@utas.edu.au~~~~~~~liguoliang@tsinghua.edu.cn\\
}


\begin{document}

\pagestyle{plain}
 \pagenumbering{arabic}

\maketitle
%
\begin{abstract}
Internet users are shifting from searching on traditional media to social network platforms (SNPs) to retrieve up-to-date and valuable information. SNPs have two unique characteristics: frequent content update
and small world phenomenon. However, existing works are not able to
support these two features simultaneously.
To address this problem,
we develop a general framework to enable real time personalized top-k query.
Our framework is based on a general ranking function that incorporates
time freshness, social relevance and textual similarity.
To ensure efficient update and query processing,
there are two key challenges. The first is to design an index structure that is update-friendly while supporting instant query processing. The second is to efficiently compute the social relevance in a complex graph. To address these challenges, we first
design a novel 3D cube inverted index to support efficient pruning on the three dimensions simultaneously. Then we devise a cube threshold based algorithm to retrieve the top-k results,
%We propose several optimizations to improve social distance calculation and optimize the 3D list via a hierarchical partition method which further enhances the pruning on the social dimension.
and propose several pruning techniques to optimize the social distance calculation, whose cost dominates the query processing. Furthermore, we optimize the 3D index via a hierarchical partition method to enhance our pruning on social dimension.
Extensive experimental results on two real-world large datasets demonstrate the efficiency and the robustness of our proposed solution.

% with an average 4-8x speedup for most of the cases.
%We focus on the 3 most important dimensions on SNPs

%Keyword search helps user to explore effectively among the shear volume of information on the social network platforms. Naturally people care about information that is more socially related. Moreover chronological ordering, usually ignored by existing work, should also be considered in the ranking of query results to enhance user's search experience. In this paper, we formulate the real time personalized query model that consists of time, social and textual dimension for ranking the search results. An 3D index that incorporate 3 dimensions simultaneously is designed for both fast updating and powerful pruning. An efficient CubeTA algorithm is further devised for retrieving top-k results from the 3D index.

%The key challenge to our problem is the computation on the social dimension. By making use of the \emph{small world} property of the social network, we first propose several pruning strategies to quickly evaluate the social relevance scores of the candidate records. Then by deploying a time-aware dynamic graph partition scheme, we provide extra flexibility for 3D index that balance between the query performance and index size. Extensive experimental study on 2 large real world dataset has confirmed the superiority of the index design and query processing techniques.
\end{abstract}

\input{Introduction}
\input{Related-Work}
\input{Problem-Definition}
\input{Index-Design}
\input{Query-Processing}
\input{Shortest-Path}
\input{Index-Optimization}
\input{Experiment-Results}
\input{Conclusion}

% NOTE keywords are not used for conference papers so do not populate them
% \begin{keywords}
% keyword-1, keyword-2, keyword-3
% \end{keywords}
%
\bibliographystyle{IEEEtran}
\vspace{-1mm}
\bibliography{reference}


\end{document}
